/*
 * @lc app=leetcode.cn id=2163 lang=cpp
 *
 * [2163] 删除元素后和的最小差值
 */

// @lc code=start
class Solution
{
public:
    long long minimumDifference(vector<int> &nums)
    {
        int m = nums.size(), n = m / 3;
        long long lsum[m], ltotal = 0;
        // priority_queue<long long> heap;
        multiset<long long> heap;
        for (int i = 0, sum = 0; i < m; i++)
        {
            ltotal += nums[i];
            lsum[i] = 0;
            // heap.push(nums[i]);
            heap.insert(-nums[i]);
            if (heap.size() < n)
            {
                continue;
            }
            if (heap.size() > n)
            {
                // sum += heap.top();
                // heap.pop();
                sum -= *(heap.begin());
                heap.erase(heap.begin());
            }
            lsum[i] = sum;
        }

        long long rtotal = 0, ans = INT_MAX;
        // heap = priority_queue<long long>();
        heap.clear();
        for (int i = m - 1, sum = 0; i >= n; i--)
        {
            ltotal -= nums[i];
            rtotal += nums[i];
            // heap.push(-nums[i]);
            heap.insert(nums[i]);
            if (heap.size() < n)
            {
                continue;
            }
            if (heap.size() > n)
            {
                // sum -= heap.top();
                // heap.pop();
                sum += *(heap.begin());
                heap.erase(heap.begin());
            }
            ans = min(ans, (ltotal - lsum[i - 1]) - (rtotal - sum));
        }

        return ans;
    }
};
// @lc code=end
